package n143;

import static n143.Solution.genNext;

/**
 * @author 苏文广
 * @since 2021/10/2
 */
public class Solution2 {

    // 找到链表中点
    // 将后半段链表逆序
    // 合并链表
    public static void main(String[] args) {
        // 构造链表
        Solution.ListNode head = genNext();
        reorderList(head);
        System.out.println(head);
    }

    private static void reorderList(Solution.ListNode head) {
        // 找链表中点
        Solution.ListNode middleNode = middleNode(head);
        // 逆转后半段链表
        Solution.ListNode reverse = reverse(middleNode);
        // 合并链表
        Solution.ListNode ptr = head;
        while (ptr != middleNode) {
            Solution.ListNode temp = ptr.next;
            ptr.next = reverse;
            ptr = temp;

            temp = reverse.next;
            reverse.next = ptr;
            reverse = temp;
        }

        // 奇数时, ptr 结束时为middleNode, 偶数时 ptr 结束时也为middleNode
        if (ptr.next == ptr) {
            // 解决奇数时, ptr 自身循环问题
            ptr.next = null;
        }
    }

    /**
     * 翻转链表
     *
     * @param node 头结点
     * @return 翻转后的头结点
     */
    private static Solution.ListNode reverse(Solution.ListNode node) {
        if (node.next == null) {
            return node;
        }
        Solution.ListNode reversHead = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return reversHead;
    }

    // 快慢指针 找 链表中点
    private static Solution.ListNode middleNode(Solution.ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        Solution.ListNode slow = head;
        Solution.ListNode fast = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }


}
